// https://leetcode.cn/problems/course-schedule-ii/

// 题干：现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，
//      其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
//      例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
//      返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。
//      如果不可能完成所有课程，返回 一个空数组 。

// 示例：输入：numCourses = 2, prerequisites = [[1,0]]
//      输出：[0,1]

// 碎语：同课程表1类似

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
    {
        // 1.准备工作
        vector<vector<int>> edges(numCourses); // 邻接表存图
        vector<int> in(numCourses); // 存储每一个点的入度

        // 2,建图
        for (const auto& v : prerequisites)
        {
            int a = v[0], b = v[1]; //  b -> a
            edges[b].push_back(a);
            in[a]++;
        }

        // 3.拓扑排序
        queue<int> q;
        vector<int> ret;
        for (int i = 0 ; i < numCourses ; i++){
            if (!in[i]) q.push(i);
        }
        while (q.size()){
            int t = q.front(); q.pop();
            ret.push_back(t);
            for (const auto& a : edges[t])
            {
                in[a]--;
                if (!in[a]) q.push(a);
            }
        }

        // 4.判断
        if (ret.size() == numCourses) return ret;
        else return {};
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> prerequisites = {{1, 0}};

    vector<int> index = sol.findOrder(2, prerequisites);
    for (const auto& num : index) cout << num << " ";
    cout << endl;

    return 0;
}